package com.itheima.entry;

//快排
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={45,2,34,78,21,23,14,74,35};
        int left=0;
        int right=arr.length-1;
      quickSort(arr,left,right);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"  ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        if(right<left) {
            return ;
        }
        int left0=left;
        int right0=right;
        int num=arr[left0];
        //定位基准数的位置
        while (left!=right){
      //先进行右边数据的判断，在进行左边数据的判断
            //右边的数组数据大于等于基准数，则right--
            while (arr[right]>=num&&right>left){
                right--;
            }
            //左边的数组数据小于等于基准数，则left++
            while (arr[left]<=num&&right>left){
                left++;
            }
            //当基准数比左边数据小，比右边数据大，则交换这两个数据
            int  temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
        }
        //基准数归位置
        int temp=arr[left];
        arr[left]=arr[left0];
        arr[left0]=temp;
        quickSort(arr,left0,left-1);
        quickSort(arr,right+1,right0);

    }
}
